package main

import "fmt"

//#link: https://leetcode-cn.com/problems/combination-sum/
func main() {
	candidates := []int{2, 3, 6, 7}
	target := 7
	fmt.Println(combinationSum(candidates, target))
}

var result [][]int

func combinationSum(candidates []int, target int) [][]int {
	result = make([][]int, 0)
	backTrace(candidates, []int(nil), 0, target)
	return result
}

func backTrace(candidates, path []int, idx, target int) {
	if idx == len(candidates) {
		return
	}
	if target == 0 {
		result = append(result, append([]int(nil), path...))
		return
	}
	//跳过当前数
	backTrace(candidates, path, idx+1, target)
	if target-candidates[idx] >= 0 {
		path = append(path, candidates[idx])
		backTrace(candidates, path, idx, target-candidates[idx])
		path = path[:len(path)-1]
	}
}
